package crack.ch1;

/**
 * @author Pavel Belevich
 *         Date: 6/30/12
 *         Time: 6:45 PM
 */
/*
Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0.
 */
public class Problem7 {

    public static void main(String[] args) {
        int M = 10;
        int N = 15;
        int[][] matrix = new int[M][N];
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                matrix[i][j] = Math.random() > 0.05 ? 1 : 0;
                if (matrix[i][j] == 0) {
                    System.out.print("0\t");
                } else {
                    System.out.print(" \t");
                }
            }
            System.out.println();
        }

        int D = Math.min(M, N);
        for (int k = 0; k < D; k++) {
            int imin = -1;
            int jmin = -1;
            for (int i = k ; i < M ; i++) {
                if (matrix[i][k] == 0) {
                    if (imin < 0) {
                        imin = i;
                        for (i = 0 ; i < M ; i++) {
                            matrix[i][k] = 0;
                        }
//                        System.out.println();
//                        print(M, N, matrix);
                        break;
                    }
                }
            }
            for (int j = k ; j < N ; j++) {
                if (matrix[k][j] == 0) {
                    if (jmin < 0) {
                        jmin = j;
                        for (j = 0 ; j < N ; j++) {
                            matrix[k][j] = 0;
                        }
//                        System.out.println();
//                        print(M, N, matrix);
                        break;
                    }
                }
            }
            if (imin >= 0 && jmin < 0) {
                matrix[imin][k+1] = 0;
            }
            if (imin < 0 && jmin >= 0) {
                matrix[k+1][jmin] = 0;
            }
            if (imin >= 0 && jmin >= 0) {
                matrix[imin][jmin] = 0;
                imin = -1;
                jmin = -1;
//                System.out.println();
//                print(M, N, matrix);
            }
        }
        System.out.println();
        print(M, N, matrix);
    }

    private static void print(int m, int n, int[][] matrix) {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    System.out.print("0\t");
                } else {
                    System.out.print(" \t");
                }
//                System.out.print(matrix[i][j] + "\t");
            }
            System.out.println();
        }
    }

}
